|
In computer science, a 2–3 tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.〔, p.145-147〕 2−3 trees were invented by John Hopcroft in 1970. Image:2-3-4 tree 2-node.svg|2 node Image:2-3-4-tree 3-node.svg|3 node 2–3 trees are an isometry of AA trees, meaning that they are equivalent data structures. In other words, for every 2–3 tree, there exists at least one AA tree with data elements in the same order. 2–3 trees are balanced, meaning that each right, center, and left subtree contains the same or close to the same amount of data. == Definitions == We say that a node is a 2-node if and only if it has ''one'' data element and ''two'' children if it is an internal node. We say that a node is a 3-node if and only if it has ''two'' data elements and ''three'' children if it is an internal node. We say that is a 2-3 tree if and only if one of the following statements hold: * is empty. In other words, does not have any nodes. * is a 2-node with data element . If has left child and right child , then * * and are non-empty 2-3 trees of the same height, * * is greater than each element in , and * * is less than or equal to each data element in . * is a 3-node with data elements and , where . If has left child , middle child , and right child , then * * , , and are non-empty 2-3 trees of equal height, * * is greater than each data element in and less than or equal to each data element in , and * * is greater than each data element in and less than or equal to each data element in . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「2–3 tree」の詳細全文を読む スポンサード リンク
|